package org.leetcode.easy.leetcode111;

import org.leetcode.TreeNode;

public class Solution
{

    //最小深度就是计算根节点到最近叶子节点的距离
    public int minDepth2(TreeNode root){

        if (root==null){
            return 0;
        }

        //左子树的最小深度
        int minLeft = minDepth2(root.left);
        //右子树的最小深度
        int minRight = minDepth2(root.right);

        //如果左侧为空
        if (root.left==null){
            return minRight+1;
        }

        //如果右侧为空
        if (root.right==null){
            return minLeft+1;
        }
        //如果左右都不为空
        int midDepth = Math.min(minLeft,minRight)+1;

        return midDepth;

    }

    public int minDepth(TreeNode root) {

        if (root==null)
        {
            return 0;
        }

        //左子树为空，右不为空
        if (root.left==null)
        {
            return minDepth(root.right)+1;
        }
        if (root.right==null)
        {
            return minDepth(root.left)+1;
        }

        int minLeftDepth = minDepth(root.left);
        int minRightDepth = minDepth(root.right);

        return Math.min(minLeftDepth,minRightDepth)+1;

    }

    public static void main(String[] args) {
//        // 创建叶子节点
//        TreeNode leftLeafOfRightNode = new TreeNode(15);
//        TreeNode rightLeafOfRightNode = new TreeNode(7);
//
//// 创建中间层节点
//        TreeNode leftMid = new TreeNode(9); // 由于9节点没有子节点，所以不用进一步添加
//        TreeNode rightMid = new TreeNode(20, leftLeafOfRightNode, rightLeafOfRightNode);
//
//// 创建根节点
//        TreeNode root = new TreeNode(3, leftMid, rightMid);


        // 首先创建叶子节点
        TreeNode node15 = new TreeNode(15);
        TreeNode node7 = new TreeNode(7);

// 接着创建20节点，它有两个子节点
        TreeNode node20 = new TreeNode(20, node15, node7);

// 创建9节点，这里9没有子节点，所以直接创建
        TreeNode node9 = new TreeNode(9);

// 最后，创建根节点3，它的左右子节点分别是9和20
        TreeNode root = new TreeNode(3, node9, node20);


        Solution solution = new Solution();
        int minDepth = solution.minDepth(root);

        System.out.println(minDepth);

    }
}
